package th.retrofit.lib;

public class Solution86 {

    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) return head;
        ListNode newHead = partition(head.next, x);
        if (head.val >= x && newHead.val < x) {
            ListNode cur = newHead;
            ListNode pre = cur;
            while (cur != null && cur.val < x) {
                pre = cur;
                cur = cur.next;
            }
            pre.next = head;
            head.next = cur;
        } else {
            head.next = newHead;
            newHead = head;
        }
        return newHead;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{2, 1};
        ListNode node = ListNode.arr2Node(arr);
        System.out.println(new Solution86().partition(node, 2));
    }

}
